package leetcode_500;

import java.util.Comparator;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;

/**
 *@author 周杨
 *QueueReconstructionByHeight_406 给定一个随机队列 里面是数组 第一个元素表名身高 第二个元素表名前面有多少比其高的  求排序后的队列
 *describe:每次把当前最矮的插入  AC 44%
 *2018年7月19日 上午11:31:51
 */
public class QueueReconstructionByHeight_406 {
	public static void main(String[] args) {
		QueueReconstructionByHeight_406 test=new QueueReconstructionByHeight_406();
		int[][] res=test.reconstructQueue(new int[][] {
			{7,0},{4,4},{7,1},{5,0},{6,1},{5,2}
		});
	}
	
	public int[][] reconstructQueue(int[][] people) {
		if(people.length==0||people[0].length==0)
			return people;
        int res[][]=new int[people.length][people[0].length];
        Set<int[]> map=new TreeSet<int[]>(new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				if(o1[0]<o2[0])
					return -1;
				else if(o1[0]>o2[0])
						return 1;
				else 
					return o1[1]>o2[1]?1:-1;
			}
		});
        for(int i=0;i<people.length;++i) {
        	map.add(people[i]);
        }
        boolean judge[]=new boolean[people.length];
        
        for(int[] now:map) {
        	int index=now[1];
        	int j=0;
        	while(index!=-1) {
        		if(!judge[j]||res[j][0]>=now[0])
        			--index;
        		++j;
        	}
        	judge[j-1]=true;
        	res[j-1][0]=now[0];
        	res[j-1][1]=now[1];	
        }
        return res;
    }
}
